\documentclass{ctexart}

\usepackage{}

\title{DoubleLinkedList设计思路和测试说明}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\begin{document}
\maketitle

\section{项目设计思路}
内嵌Node类作为节点，内置常量迭代器和迭代器访问其指定位置的元素。迭代器重载了==,!=,前缀++,后缀++,*运算符。链表本身重载了=，提供了访问链表begin和end位置的迭代器、访问元素数量、访问头尾的元素并增删、及在迭代器所指的位置进行插入和删除操作的方法。
下面是我基于课本说明，增加了检验迭代器功能的部分修改代码。

\subsection{迭代器部分代码}
\begin{verbatim}
public:
    class const_iterator
    {
    public:
/// default constructor
	const_iterator():theList{nullptr},current{nullptr}{} 

    protected:
/// theList is used to make sure
/// iterator is for the correct list
	DoubleLinkedList<Object> *theList;
	Node *current;

	Object &retrieve()const
	    {return current->data;}

/// parametric constructor 
	const_iterator(DoubleLinkedList<Object> &lst,Node *p)
        :theList{&lst},current{p}{}
/// determine whether the iterator is initialized
	void assertIsValid()const 
	    {
		if(theList==nullptr||current==nullptr||current==theList->head)
		    throw IteratorOutOfBoundsException{};
	    }
    };
\end{verbatim}
首先是在迭代器中增加了一个指向自身链表的指针作为成员属性，同时增加了判断迭代器是否初始化的成员函数。

\subsection{begin和end的修改}
\begin{verbatim}
/// *this represents the DoubleLinkedList itself
/// return iterator representing begining and 
/// endmarker of the list
    iterator begin()
    	{return {*this,head->next};}
    const_iterator begin()const
        {return {*this,head->next};}
    iterator end()
	{return {*this,tail};}
    const_iterator end()const
	{return {*this,tail};}
\end{verbatim}
因为修改了iterator，所以begin和end的返回作了相应的修改。

\subsection{insert和erase的修改}
\begin{verbatim}
///insert x before itr
    iterator insert(iterator itr,const Object &x)
	{
	    itr.assertIsValid();
	    if(itr.theList!=this)
		throw IteratorMismatchException{};
	    
	    Node *p=itr.current;
	    theSize++;
	    return {*this,p->prev=p->prev->next=new Node{x,p->prev,p}};
	}

///erase item at itr
    iterator erase(iterator itr)
	{
	     itr.assertIsValid();
	    if(itr.theList!=this)
	        throw IteratorMismatchException{};
	    else if(itr==this->end())
		throw IteratorOutOfBoundsException{};
	    
	    Node *p=itr.current;
	    iterator retVal{*this,p->next};
	    p->prev->next=p->next;
	    p->next->prev=p->prev;
	    delete p;
	    theSize--;
	    return retVal;
	}
\end{verbatim}
在insert和erase中调用了asserIsValid判断迭代器是否初始化，同时增加了对迭代器是否正确的判断，并给出了相应的异常处理。

\subsection{find函数的定义}
\begin{verbatim}
/// traverse through the list to find
/// whether the _val is in the _list
/// if it is found,return its iterator,otherwise return
/// iterator representing endmarker of the list
    iterator find(DoubleLinkedList<Object>& _list,
    const Object& _val)const
{
    for(iterator itr=_list.begin();itr !=_list.end();++itr)
    {
	if(*itr==_val)
	    return itr;
    }
    std::cout <<"没有找到" <<_val<<std::endl;
    return _list.end();
}
    iterator find(DoubleLinkedList <Object>& _list,
    Object&& _val)const
{
    for(iterator itr=_list.begin();itr !=_list.end();++itr)
    {
	if(*itr==std::move(_val))
	    return itr;
    }
    std::cout <<"没有找到" <<_val<<std::endl;
    return _list.end();
}
\end{verbatim}
这是作业要求中的用于查找值的函数，我把它放在类内实现，并提供了左值和右值输入两个版本的函数。如果没有找到\_val，我通过输出来与用户实现交互，同时自然地将没有对应数据的\_list.end()作为返回值。

\section{测试说明}
\subsection{测试代码}
下面是main.cpp中的代码部分。printList()函数提供了对参数为<int>的list的遍历输出，test()函数中对迭代器异常进行了测试，并捕获了相关异常。test()中分别测试了未初始化的迭代器、错误的迭代器、迭代器范围输入错误三种错误类型。main()函数中则按照作业要求进行了操作。
\begin{verbatim}
#include"DoubleLinkedList.h"
#include<iostream>

///打印DoubleLinkedList<int>类的链表
void printList(DoubleLinkedList<int> &_list)
{
    DoubleLinkedList<int>::iterator itr=_list.begin();
    std::cout<<"["<<*(itr++);
    for(;itr!=_list.end();++itr)
    {
	std::cout<<","<<*itr;
   }
    std::cout<<"]"<<std::endl;
}

///测试改进后的迭代器错误时的异常处理
void test()
{
    DoubleLinkedList<int>list1;
    DoubleLinkedList<int>list2;
    for(int i=1;i<=5;i++)
	list1.push_back(i);
    for(int i=1;i<=5;i++)
	list2.push_back(10-i);

    DoubleLinkedList<int>::iterator itr1;
    DoubleLinkedList<int>::iterator itr2=list2.begin();
    DoubleLinkedList<int>::iterator itr3=list2.end();
    try
    {
	list1.erase(itr1);///<未初始化的迭代器
	list1.insert(itr1,6);
    }
    catch(IteratorOutOfBoundsException s1){}
    try
    {
        list1.erase(itr2);///<错误的迭代器
	list1.insert(itr2,6);
    }
    catch(IteratorMismatchException s2){}
    try
    {
        list2.erase(itr3,itr2);///<迭代器范围输入错误
    }
    catch(IteratorOutOfBoundsException s3){}
    printList(list1);
    printList(list2);
}

int main(int argc,char *argv[])
{
    DoubleLinkedList<int> L;
    for(int i=1;i<=5;i++)
	L.push_back(i);

    printList(L);
    
    DoubleLinkedList<int>::iterator iter=L.find(L,3);
    if(iter!=L.end())///<判断是否找到3,若找到再进行删除操作
    {
	L.erase(iter);
    }
    
    printList(L);
    iter=L.find(L,3);

    test();///调用测试函数
    
    return 0;
}
\end{verbatim}

\subsection{测试结果}
main()函数操作过程与结果记录如下：
\\A.创建链表 L;
\\(gdb)L= {theSize = 0, head = 0x55555556beb0, tail = 0x55555556bed0}
\\B.用push\_back依次插入1,2,3,4,5;
\\(gdb)L= {theSize = 5, head = 0x55555556beb0, tail = 0x55555556bed0}
\\C.输出L;
\\\lbrack1,2,3,4,5\rbrack
\\D.iter = find(L, 3);
\\(gdb)iter= {<DoubleLinkedList<int>::const\_iterator> = {theList =
\\0x7fffffffde20, current = 0x55555556bf30}, <No data fields>}
\\E.erase(iter);
\\(gdb)L= {theSize = 4, head = 0x55555556beb0, tail = 0x55555556bed0}
\\F.输出L;
\\\lbrack1,2,4,5\rbrack
\\G.iter = find(L, 3).
\\没有找到3
\\(gdb)iter= {<DoubleLinkedList<int>::const\_iterator> = {theList =
\\0x7fffffffde20, current = 0x55555556bed0}, <No data fields>}
\\H.test调用
\\iterator out of bounds exception
\\iterator mismatch exception
\\iterator out of bounds exception
\\\lbrack1,2,3,4,5\rbrack
\\\lbrack9,8,7,6,5\rbrack

\subsection{内存泄露检查}
使用valgrind进行内存检查，结果如下，没有内存泄露：
\\==6586== Memcheck, a memory error detector
\\==6586== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
\\==6586== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
\\==6586== Command: test
\\==6586== 
\\==6586== 
\\==6586== HEAP SUMMARY:
\\==6586==     in use at exit: 0 bytes in 0 blocks
\\==6586==   total heap usage: 30 allocs, 30 frees, 4,073 bytes allocated
\\==6586== 
\\==6586== All heap blocks were freed -- no leaks are possible
\\==6586== 
\\==6586== For lists of detected and suppressed errors, rerun with: -s
\\==6586== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
\end{document}
